Методи попередніх еквівалентних перетворень та ітераційні методи з мінімізацією нев`язки

Реферат «Введення в чисельні методи»
Тема: «Методи попередніх еквівалентних перетворень та ітераційні методи з мінімізацією нев'язки для розв'язування СЛАР»

1. Методи попередніх еквівалентних перетворень
1.1 Перетворення обертання
Наступний важливий підхід до вирішення алгебраїчних систем рівнянь базується на застосуванні еквівалентних перетворень за допомогою унітарних матриць, що зводить початкову матрицю до еквівалентної їй діагональної.
Сенс цього підходу полягає в тому, щоб послідовно, множенням зліва і / або праворуч на спеціальні унітарні матриці, перетворити деякі компоненти вихідної матриці в нуль.
Матриця S називається унітарною, якщо її твір зі своєю комплексно спряженої одно одиничної матриці. Це означає, що комплексно спряжена матриця дорівнює зворотної матриці:

Відомою унітарної матрицею є матриця обертання, яка застосовується для повороту на заданий кут вектора, що належить деякій площині, навколо початку координат. У двовимірному випадку вектор повертається на кут шляхом множення на матрицю

Щоб зберегти еквівалентність результуючої матриці при множенні її на матрицю обертання, необхідно початкову матрицю множити праворуч на і ліворуч на . Множення ж матриці обертання на вектор дає такий же за величиною вектор, але повернений на заданий кут.
Поворот вектора в багатовимірному просторі на довільний кут можна уявити, як послідовність плоских обертань кожної проекції на деякий кут. Якщо підібрати кут обертання так, щоб у плоскому повороті одну з проекцій вектора поєднати з координатною віссю, то друга проекція в цій площині стає рівною нулю.
Приватні повороти вектора в багатовимірному просторі за допомогою матриці обертання можна виконувати, якщо її розширити до матриці розміру наступним чином:
.
Індекси i, j позначають матрицю обертання, що повертає вектор у площині на кут .
Тепер приватне еквівалентне перетворення матриці A обертанням на кут записуються так:
.
Умова перетворення в нуль ij-тих елементів симетричної матриці A можна отримати методом невизначених коефіцієнтів на двовимірної матриці:
.
.

Кут повороту, при якому , Знаходиться з рівняння
.
Розділивши на і позначивши , , Одержимо квадратне рівняння для тангенса необхідного кута повороту
.
З двох рішень для тангенса вибирається таке, щоб . У цьому випадку . Підставивши вираз для кута в співвідношення для діагональних елементів, після тригонометричних перетворень виходять такі формули:

Для отримання результуючої матриці виконувати матричне множення трьох матриць зовсім необов'язково. Структура матриць обертання викликає при множенні зміна тільки тих елементів вихідної матриці, які знаходяться на i-тої та j-тої рядках і на i-тому і j-тому стовпцях. Зміни представляються сумами елементів, що стоять в рядках і стовпцях, помножених на синус або косинус кута відповідно до формулами, де j> i:
перетворення рядків - ;
перетворення стовпців - .
На перетинах i-го рядка і i-того стовпця і j-го рядка і j-того стовпця розташовуються відповідно обчислені вище і , А на місцях ij-того і ji-того елементів вставляються нулі.
Для приведення до діагональної матриці необхідно виконати таких елементарних перетворень.
1.2 Ортогональні перетворення відображенням
Наступною важливою унітарної матрицею, за допомогою якої в різних алгоритмах виконуються ортогональні перетворення, є матриці відображення. Використання цього інструменту дозволяє, наприклад, послідовними еквівалентними перетворень-нями звести вихідну матрицю до верхньої трикутної (QR-алгоритми), трьох або двох діагональним і т.д.
Сенс цього підходу полягає в тому, щоб множенням матриці A зліва на спеціально підібрану унітарну матрицю   один з стовпців початкової матриці (наприклад, ) Перетворити у вектор, паралельний одиничного координатного вектору ( або ). Тоді, послідовно підбираючи потрібні унітарні матриці і відповідні одиничні вектори , Після n циклів еквівалентних перетворень можна буде отримати верхню трикутну матрицю:


При виборі в якості початкового вектора і множення матриці A на ортогональні матриці справа в кінцевому рахунку можна отримати нижню трикутну матрицю.
Все питання полягає в тому, як формувати унітарну матрицю з заданими властивостями із векторів і стовпців матриці A.
З аналітичної геометрії відомо, що будь-які вектори, що лежать у площині, взаємно перпендикулярні з її нормаллю, тобто їх проекції на нормаль дорівнюють нулю. Остання еквівалентно рівності нулю скалярних творів.
Щоб (k + 1) - мірний векторний трикутник зробити паралельним k-мірної гіперплощини з нормаллю n (вектор одиничної довжини, перпендикулярний площині), необхідно прирівняти нулю скалярний твір: (n, y) = 0.
Нехай вектор z не паралельний площині, заданої своєї нормаллю, тоді його проекції на цю площину і нормаль відповідно будуть представлені векторами і . Вектор z і вектор дзеркально-симетричний йому через ці проекції можна виразити так:

Дозволивши перше щодо і підставивши його в , Отримаємо


Проекцію вектора можна замінити скалярним добутком (n, z) і підставити у вираз для , Висловивши тим самим дзеркально відбитий вектор через вихідний вектор і нормаль гіперплощини:

Тут M являє унітарну матрицю, перетворюючу довільний вектор в дзеркально відбитий. У тому, що матриця унітарна, неважко переконатися, перевіривши її твір зі своєю комплексно спряженої:

Вираз для дзеркально відбитого вектора дозволяє уявити нормальний вектор у вигляді лінійної функції від заданого вектора z:

Число в знаменнику є нормуючим множником. Нормальний вектор представляє гіперплощина зобов'язаний мати одиничну довжину. Коефіцієнт , Який в загальному випадку є комплексним числом, необхідно вибрати так, щоб скалярний добуток було більше нуля. Якщо врахувати співвідношення для узгоджених норм: , То


Вибравши для комплексних матриць або - Для дійсних матриць, будемо мати

Таке нормування не порушує колінеарності відбитого і одиничного векторів:


Розглянемо приклад впливу ортогонального перетворення на матрицю
.




Наведена методика отримання унітарних (і ортогональних зокрема) матриць використовується в багатьох стандартних алгоритмах як інструмент часткового перетворення початкових матриць до двох або трьох діагональним, для яких у подальшому застосовуються рекурентні формули отримання рішення рівнянь, звані в літературі методом прогонки для систем з стрічковими матрицями .

2. Ітераційні методи з мінімізацією нев'язки
2. 1 Прискорення збіжності ітераційних методів
Точні методи отримання рішень, що використовують розглянуті еквівалентні перетворення повністю заповненої матриці, вимагають виконання числа операцій, пропорційного кубу розмірності системи, і вільної пам'яті для зберігання вихідних та проміжних значень - пропорційної квадрату розміру матриці. Тому для понад великих систем (число невідомих більше декількох сотень) орієнтуються в основному на застосування наближених, ітераційних методів.
Привабливість тих чи інших ітераційних методів визначається швидкістю збіжності ітераційного процесу. Теоретично доведено, що ітераційний процес Гауса-Зейделя сходиться до вирішення при будь-якому початковому значенні шуканого значення вектора рішень, однак кількість ітераційних циклів може у багато разів перевищувати число невідомих (розмірність матриці). Це викликало до життя безліч модифікацій алгоритмів, що володіють більшою швидкістю збіжності.
Процедури прискорення пов'язані з побудовою чергового вектора по одному або декільком його значенням на попередніх ітераційних циклах. Фактично мова йде про побудову на кожному кроці ітерацій інтерполює функції з векторним аргументом, за якою обчислюють черговий вектор для підстановки. Для обчислення вектора на (k + 1) - му кроці ітерацій необхідно спочатку отримати величину і одиничний вектор напрямку і підсумувати попередній вектор з додатковим вектором:
.

Підстановка останнього в рівняння ( ) Утворює вектор з покомпонентний нев'язок. Для завдання структурної взаємозв'язку кожної нев'язки з відповідною компонентою вектора і освіти функціоналу (скалярної функції від вектора нев'язок) возмем скалярний добуток вектора нев'язки на вектор-рядок :
.
Після підстановки чергового вектора функціонал отримає нове значення, яке буде залежати від деякого скаляра :
.
Щоб нев'язки на кожному кроці ітерацій ставали менше, бажано відповідним чином вибирати . Знайдемо таке значення , При якому . Для цього прирівняємо похідну за нулю. Індекс номера ітерації поки опустимо.


З останнього рівності для (k + 1) - й ітерації величина кроку в напрямку вектора повинна бути обчислена так:
.

Якщо одиничні вектори напрями послідовно вибирати рівними координатним, тобто , То буде реалізовано метод Гауса-Зейделя (метод покоординатного спуску в задачах оптимізації).
Вибираючи напрям зміни чергового вектора в бік локального убування, тобто у бік, протилежний вектору градієнта функціонала, виходить метод швидкого спуску. У цьому випадку

2.2 Метод спряжених напрямків
Серед методів, пов'язаних з вибором напрямку існують методи, в яких до векторів напрямків пред'являються вимоги їх взаємної спряженості , Тобто матриця A перетворює вектор у вектор, ортогональний вектору . Доведено, що вибір напрямів з безлічі сполучених дозволяє при будь-якому початковому звести задачу до точного розв'язання не більше, ніж за n кроків, якщо матриця симетрична і позитивно певна ( ) Розміру .
Класичним набором пов'язаних векторів є власні вектори матриці ( ). Проте завдання їх визначення складніше рішення заданої системи рівнянь. Не менш складна й завдання побудови довільної системи ортогональних векторів.
У той же час прикладом ортогональних напрямків є напрямки вектора градієнта і нормалі в заданій точці деякої гіперповерхні. Така поверхня вище була представлена ​​функціоналом у вигляді скалярного добутку вектора нев'язки і вектора x, яка і визначала напрямок спуску по напрямку градієнта. Якщо, використовуючи такий же підхід до обчислення , У виразі для останнього вектор нев'язок додатково модифікувати, як показано нижче, то рекуррентно обчислювані чергові напрями виявляться сполученими:

Вибравши на початку ітерацій і , Після виконання наведених обчислень в (n-1) циклі будуть отримані вектори напрямків, що задовольняють співвідношенням
,
а вектори нев'язок будуть ортогональними:
.
Щодо методу спряжених градієнтів доводиться, що, якщо матриця (позитивно певна і симетрична) має тільки m (m <n) різних власних значень, то ітераційний процес сходиться не більше, ніж за m ітерацій. Однак у практичній реалізації швидкість збіжності істотно залежить від величини заходи обумовленості і в ітераційному процесі може бути оцінена згідно нерівності:
,

де - Коефіцієнт, ступінь якого на кожному кроці ітераційного процесу показує у скільки разів зменшилася відстань до вектора точного рішення x *.
Чим більше , Тим ближче a до одиниці і, отже, ступеня a зменшуються повільніше. У літературі описуються модифіковані методи спряжених градієнтів, які тим чи іншим способом включають в ітераційний процес подібні (конгруентні - для комплексних матриць) перетворення, попередньо зменшують міру обумовленості.

Література
1. Бахвалов І.В. Чисельні методи. БІНОМ, 2008. - 636c.
2. Волков О.О. Чисельні методи. Вид-во Лань, 2004. - 256.
3. Демидович Б.П., ред., Марон І.А., Шувалова Е.З. Чисельні методи аналізу. Видавництво Лань, 2008.
4. Пантелєєв А.В., Кірєєв В.І., Пантелєєв В.І., Кірєєв А.В. Чисельні методи в прикладах і задачах. М: Вища школа, 2004. - 480c.
5. Пірумов Н.Р., Пірумов О.Г. Чисельні методи. Вид-во: ДРОФА, 2004. - 224c.